COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	(declare (fasload meter fas dsk (tim lsp)))
C00007 00003	(fasload meter)
C00011 ENDMK
C⊗;
(declare (fasload meter fas dsk (tim lsp)))
(declare (setq meter:meterp t))
(meter:begin fft)

(meter-funs ((cos "COSINE's")(SIN "SINE's")(1- "1-'s")(= "='s")
	     (1+ "1+'s")(store "Asets")
	     (- "-'s")(+ "+'s")(↑ "↑'s")(+$ "+$'s")(-$ "-$'s")(arraycall "Arefs")
	     (setq "Setq's")(//$ "//$'s")(*$ "*$'s")(// "//'s")
	     (float "Float's")(> ">'s")(< "<'s"))
(DEFUN FFT					        ;Fast Fourier Transform
  (AREAL AIMAG)                                         ;AREAL = real part
  (PROG							;AIMAG = imaginary part
   (AR AI PI I J K M N LE LE1 IP NV2 NM1 UR UI WR WI TR TI)
    (SETQ AR (GET AREAL 'ARRAY))			;Initialize
    (SETQ AI (GET AIMAG 'ARRAY))
    (SETQ PI 3.141592653589793)
    (SETQ N (CADR (ARRAYDIMS AR)))
    (SETQ N (1- N))
    (SETQ NV2 (// N 2))
    (SETQ NM1 (1- N))
    (SETQ M 0)						;Compute M = log(N)
    (SETQ I 1)
   L1 (COND
       ((< I N)(SETQ M (1+ M))(SETQ I (+ I I))(GO L1)))
    (COND ((NOT (EQUAL N (↑ 2 M)))
	   (PRINC "Error ... array size not a power of two.")
	   (READ)
	   (RETURN (TERPRI))))
    (SETQ J 1)						;Interchange elements
    (SETQ I 1)						;in bit-reversed order
   L3 (COND ((< I J)
	     (SETQ TR (ARRAYCALL FLONUM AR J))
	     (SETQ TI (ARRAYCALL FLONUM AI J))
	     (STORE (ARRAYCALL FLONUM AR J) (ARRAYCALL FLONUM AR
I))
	     (STORE (ARRAYCALL FLONUM AI J) (ARRAYCALL FLONUM AI
I))
	     (STORE (ARRAYCALL FLONUM AR I) TR)	
	     (STORE (ARRAYCALL FLONUM AI I) TI)))
    (SETQ K NV2)
   L6 (COND ((< K J) (SETQ J (- J K))(SETQ K (// K 2))(GO L6)))
    (SETQ J (+ J K))
    (SETQ I (1+ I))
    (COND ((< I N)(GO L3)))
    (DO L 1 (1+ L) (> L M)				;Loop thru stages
	(SETQ LE (↑ 2 L))
	(SETQ LE1 (// LE 2))
	(SETQ UR 1.0)
	(SETQ UI 0.0)
	(SETQ WR (COS (//$ PI (FLOAT LE1))))
	(SETQ WI (SIN (//$ PI (FLOAT LE1))))
 	(DO J 1 (1+ J) (> J LE1)			;Loop thru butterflies
 	    (DO I J (+ I LE) (> I N)			;Do a butterfly
		(SETQ IP (+ I LE1))
		(SETQ TR (-$ (*$ (ARRAYCALL FLONUM AR IP) UR)
			     (*$ (ARRAYCALL FLONUM AI IP) UI)))
		(SETQ TI (+$ (*$ (ARRAYCALL FLONUM AR IP) UI)
			     (*$ (ARRAYCALL FLONUM AI IP) UR)))
		(STORE (ARRAYCALL FLONUM AR IP)
		       (-$ (ARRAYCALL FLONUM AR I) TR))
		(STORE (ARRAYCALL FLONUM AI IP)
		       (-$ (ARRAYCALL FLONUM AI I) TI))
		(STORE (ARRAYCALL FLONUM AR I)
		       (+$ (ARRAYCALL FLONUM AR I) TR))
		(STORE (ARRAYCALL FLONUM AI I)
		       (+$ (ARRAYCALL FLONUM AI I) TI)))
	    (SETQ TR (-$ (*$ UR WR) (*$ UI WI)))
	    (SETQ TI (+$ (*$ UR WI) (*$ UI WR)))
	    (SETQ UR TR)
	    (SETQ UI TI)))
    (RETURN T))))


;;; Sets up the two arrays
(SETQ RE (ARRAY RE FLONUM 1025.))

(SETQ IM (ARRAY IM FLONUM 1025.))

;;; The timer which does 10 calls on FFT

(include "timer.lsp")
(timer timit 
       (fft 're 'im))

(meter:end)
(fasload meter)
(fasload fft sas)
(fasload ttime fas dsk (mac lsp))
(timit)
(meter:report)
Timing performed on Monday 02/28/83 at 23:08:14.
Cpu (- GC) Time = 4.498
Elapsed Time = 657.45
Wholine Time = 274.633335
GC Time = 0.783
Load Average Before  = 2.92678034
Load Average After   = 1.94354212
Average Load Average = 2.43516123
NIL 
Statistics
= <calls> (<percentage>) [runtime (<percentage>)]

Meter for: FFT
Setq's = 26462 (14.88%) [2.755 (36.91%)]
1-'s = 4 (0.0%) 	[0.0 (0.0%)]
/'s = 1138 (0.64%) 	[0.014 (0.19%)]
<'s = 4572 (2.57%) 	[0.051 (0.68%)]
1+'s = 2194 (1.23%) 	[0.018 (0.24%)]
+'s = 11401 (6.41%) 	[0.087 (1.17%)]
↑'s = 12 (0.01%) 	[1.0E-3 (0.01%)]
Arefs = 43384 (24.4%) 	[0.412 (5.52%)]
Asets = 22904 (12.88%) 	[1.31 (17.55%)]
-'s = 1126 (0.63%) 	[6.0E-3 (0.08%)]
>'s = 7187 (4.04%) 	[0.069 (0.92%)]
COSINE's = 10 (0.01%) 	[1.0E-3 (0.01%)]
/$'s = 20 (0.01%) 	[0.0 (0.0%)]
Float's = 20 (0.01%) 	[0.0 (0.0%)]
SINE's = 10 (0.01%) 	[0.0 (0.0%)]
-$'s = 16383 (9.22%) 	[0.97 (12.99%)]
*$'s = 24572 (13.82%) 	[0.765 (10.25%)]
+$'s = 16383 (9.22%) 	[1.006 (13.48%)]
Total = 177782	7.465
T 
(setq meter:real-runtime 4004.0)
(meter:report)
Statistics
= <calls> (<percentage>) [runtime (<percentage>)]

Meter for: FFT
Setq's = 26462 (14.88%) [2.755 (68.81%)]
1-'s = 4 (0.0%) 	[0.0 (0.0%)]
/'s = 1138 (0.64%) 	[0.014 (0.35%)]
<'s = 4572 (2.57%) 	[0.051 (1.27%)]
1+'s = 2194 (1.23%) 	[0.018 (0.45%)]
+'s = 11401 (6.41%) 	[0.087 (2.17%)]
↑'s = 12 (0.01%) 	[1.0E-3 (0.02%)]
Arefs = 43384 (24.4%) 	[0.412 (10.29%)]
Asets = 22904 (12.88%) 	[1.31 (32.72%)]
-'s = 1126 (0.63%) 	[6.0E-3 (0.15%)]
>'s = 7187 (4.04%) 	[0.069 (1.72%)]
COSINE's = 10 (0.01%) 	[1.0E-3 (0.02%)]
/$'s = 20 (0.01%) 	[0.0 (0.0%)]
Float's = 20 (0.01%) 	[0.0 (0.0%)]
SINE's = 10 (0.01%) 	[0.0 (0.0%)]
-$'s = 16383 (9.22%) 	[0.97 (24.23%)]
*$'s = 24572 (13.82%) 	[0.765 (19.11%)]
+$'s = 16383 (9.22%) 	[1.006 (25.12%)]
Total = 177782	4.004
T